// https://leetcode.cn/problems/longest-palindromic-substring/

// 题干：给你一个字符串 s，找到 s 中最长的回文子串。
//      如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

// 示例：输入：s = "babad"
//      输出："bab"

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string expand(string s)
    {
        // 中心拓展算法

        int begin = 0, len = 0; //存储起始位置和长度

        for (int i = 0 ; i < s.size() ; i++){ // 依次枚举所有的中点
            // 先做一次奇数长度的拓展
            int left = i, right = i;
            while (left >= 0 && right < s.size() && s[left] == s[right]){
                left--;
                right++;
            }
            if (len < right - left - 1){
                len = right - left - 1;
                begin = left + 1;
            } // 注意这个时候left和right指向哪里

            // 再做一次偶数长度的拓展
            left = i, right = i + 1;
            while (left >= 0 && right < s.size() && s[left] == s[right]){
                left--;
                right++;
            }
            if (len < right - left - 1){
                len = right - left - 1;
                begin = left + 1;
            } // 注意这个时候left和right指向哪里
        }

        return s.substr(begin, len);
    }
};

int main()
{
    Solution sol;
    string s = "babad";

    string index = sol.expand(s);
    cout << index << endl;
    
    return 0;
}